from RandomList import GetRandomList

# 稳定快速排序
# 借助中间节点pivot
def stable_quick_sort(ar):
    if len(ar) <= 1:
        return ar
    else:
        mid = len(ar)//2
        pivot = ar[mid]
        smaller,greater = [],[]
        for indx, val in enumerate(ar):
            if indx != mid:
                if val < pivot:
                    smaller.append(val)
                elif val > pivot:
                    greater.append(val)
                else:
                    if indx < mid:
                        smaller.append(val)
                    else:
                        greater.append(val)
        return stable_quick_sort(smaller)+ \
            [pivot] + stable_quick_sort(greater)


     
if __name__ == "__main__":
    Arr = GetRandomList(100)
    Arr = stable_quick_sort(Arr)
    print(Arr)



